#include <iostream>
#include <vector>

using namespace std;

// -20221225- 插入排序&&希尔排序的实现

namespace MySort
{
    // 插入排序
    template<class T>
    void InsertSort(vector<T>& v)
    {
        int n = v.size();

        for (int i = 0; i < n - 1; i++)
        {
            int tmp = v[i + 1];
            int end = i;
            while (end >= 0)
            {
                if (tmp < v[end])
                {
                    v[end + 1] = v[end];
                    end--;
                }
                else break;
            }
            v[end + 1] = tmp;
        }
    }

    // 希尔排序
    template<typename T>
    void ShellSort(vector<T>& v)
    {
        int n = v.size();
        int gap = n;
        
        while (gap > 1)
        {
            gap = gap / 3 + 1;

            for (int i = 0; i < n - gap; ++i)
            {
                int tmp = v[i + gap];
                int end = i;

                while (end >= 0)
                {
                    if (tmp < v[end])
                    {
                        v[end + gap] = v[end];
                        end -= gap;
                    }
                    else break;
                }
                v[end + gap] = tmp;
            }
        }
    }
}

int main()
{
    vector<int> arr1 = {-1, 0, 0, 99, -3, 2, 3, 8, 1, -1, 100};

    MySort::ShellSort(arr1);
    for (auto e : arr1)
    {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}